# https://leetcode-cn.com/problems/unique-paths/
# 62. 不同路径

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0]*n]*m
        # print(dp)
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0):
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        #         print(dp)
        # print(dp)
        return dp[m-1][n-1]
                

a = Solution();
a.uniquePaths(3,3)